import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/*迭代*/
public class Solution2 {
    /*中序*/
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();/*另外需要注意一下linkedlist它的方法很多
        既有 其原生方法add，remove等等，也有双端队列的方法offer，poll，push，pop等*/

        while (root != null || !stack.isEmpty()) {  // 外循环是用来出栈，内循环是用来入栈，记住这个就行
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            list.add(node.val);
            root = node.right;
        }
        return list;

    }

    /*前序与中序类似略*/

    /*后序
    * 与上面的方法相比更加复杂
    * 需要注意以下几个点：
    * 1.增加了重新入栈：当右子树不空而且没被遍历过的时候
    * 2.增加前一个结点：目的是记录右子树是否被访问过
    * */
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()){
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            if (node.right == null || pre == node.right) {
                list.add(node.val);
                pre = node;
                root = null;  // 也可以不加，加上更保险，加上显得思路更清晰
            }else {
                stack.push(node);
                root = node.right;
            }

        }
        return list;

    }
}


// 希望你开心点，一起加油！
/*
     _--_  _--_
    -    \/    -
     -        -
       -    -
         -

        _
       \   \
         \    \
         |     |
        /    /
       ... `

*/